<!DOCTYPE html>
<html>
<head>
    

    

    



    <meta charset="utf-8">
    
    
    
    
    <title>快速排序和归并排序的时间复杂度分析——通俗易懂 | 博客主页 | 世界是个球，前方总有路！</title>
    <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">
    
    <meta name="theme-color" content="#3F51B5">
    
    
    <meta name="keywords" content="数据结构与算法">
    <meta name="description" content="一、前言&amp;emsp;&amp;emsp;今天面试的时候，被问到归并排序的时间复杂度，这个大家都知道是O（nlogn），但是面试官又继续问，怎么推导出来的。这我就有点懵了，因为之前确实没有去真正理解这个时间复杂度是如何得出的，于是就随便答了一波（理解了之后，发现面试的时候答错了……）。 &amp;emsp;&amp;emsp;归并排序和快速排序，是算法中，非常重要的两个知识点，同时也是在面试中被问的非常频繁的内容，我明知如">
<meta property="og:type" content="article">
<meta property="og:title" content="快速排序和归并排序的时间复杂度分析——通俗易懂">
<meta property="og:url" content="http://tewuyiang.gitee.io/blog/%E9%80%9A%E4%BF%97%E6%98%93%E6%87%82%E7%9A%84%E5%BD%92%E5%B9%B6%E6%8E%92%E5%BA%8F%E5%92%8C%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F%E6%97%B6%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6%E5%88%86%E6%9E%90/index.html">
<meta property="og:site_name" content="博客主页">
<meta property="og:description" content="一、前言&amp;emsp;&amp;emsp;今天面试的时候，被问到归并排序的时间复杂度，这个大家都知道是O（nlogn），但是面试官又继续问，怎么推导出来的。这我就有点懵了，因为之前确实没有去真正理解这个时间复杂度是如何得出的，于是就随便答了一波（理解了之后，发现面试的时候答错了……）。 &amp;emsp;&amp;emsp;归并排序和快速排序，是算法中，非常重要的两个知识点，同时也是在面试中被问的非常频繁的内容，我明知如">
<meta property="og:locale" content="zh_CN">
<meta property="article:published_time" content="2020-05-08T18:28:16.000Z">
<meta property="article:modified_time" content="2020-05-08T19:52:55.485Z">
<meta property="article:author" content="特务依昂">
<meta property="article:tag" content="数据结构与算法">
<meta name="twitter:card" content="summary">
    
        <link rel="alternate" type="application/atom+xml" title="博客主页" href="/blog/atom.xml">
    
    <link rel="shortcut icon" href="/blog/img/title.png">
    <link rel="stylesheet" href="//unpkg.com/hexo-theme-material-indigo@latest/css/style.css">
    <script>window.lazyScripts=[]</script>

    <!-- custom head -->
    

<meta name="generator" content="Hexo 4.2.0"></head>

<body>
    <div id="loading" class="active"></div>

    <aside id="menu" class="hide" >
  <div class="inner flex-row-vertical">
    <a href="javascript:;" class="header-icon waves-effect waves-circle waves-light" id="menu-off">
        <i class="icon icon-lg icon-close"></i>
    </a>
    <div class="brand-wrap" style="background-image:url(/blog/img/brand.jpg)">
      <div class="brand">
        <a href="/blog/" class="avatar waves-effect waves-circle waves-light">
          <img src="/blog/img/avatar.jpg">
        </a>
        <hgroup class="introduce">
          <h5 class="nickname">特务依昂</h5>
          <a href="mailto:1131564805@qq.com" title="1131564805@qq.com" class="mail">1131564805@qq.com</a>
        </hgroup>
      </div>
    </div>
    <div class="scroll-wrap flex-col">
      <ul class="nav">
        
            <li class="waves-block waves-effect">
              <a href="/blog/"  >
                <i class="icon icon-lg icon-home"></i>
                主页
              </a>
            </li>
        
            <li class="waves-block waves-effect">
              <a href="/blog/archives"  >
                <i class="icon icon-lg icon-archives"></i>
                博客
              </a>
            </li>
        
            <li class="waves-block waves-effect">
              <a href="/blog/tags"  >
                <i class="icon icon-lg icon-tags"></i>
                标签
              </a>
            </li>
        
            <li class="waves-block waves-effect">
              <a href="/blog/categories"  >
                <i class="icon icon-lg icon-th-list"></i>
                分类
              </a>
            </li>
        
            <li class="waves-block waves-effect">
              <a href="https://github.com/tewuyiang" target="_blank" >
                <i class="icon icon-lg icon-github"></i>
                Github
              </a>
            </li>
        
            <li class="waves-block waves-effect">
              <a href="https://weibo.com/u/5516635708/" target="_blank" >
                <i class="icon icon-lg icon-weibo"></i>
                Weibo
              </a>
            </li>
        
            <li class="waves-block waves-effect">
              <a href="https://www.cnblogs.com/tuyang1129/" target="_blank" >
                <i class="icon icon-lg icon-link"></i>
                博客园
              </a>
            </li>
        
      </ul>
    </div>
  </div>
</aside>

    <main id="main">
        <header class="top-header" id="header">
    <div class="flex-row">
        <a href="javascript:;" class="header-icon waves-effect waves-circle waves-light on" id="menu-toggle">
          <i class="icon icon-lg icon-navicon"></i>
        </a>
        <div class="flex-col header-title ellipsis">快速排序和归并排序的时间复杂度分析——通俗易懂</div>
        
        <div class="search-wrap" id="search-wrap">
            <a href="javascript:;" class="header-icon waves-effect waves-circle waves-light" id="back">
                <i class="icon icon-lg icon-chevron-left"></i>
            </a>
            <input type="text" id="key" class="search-input" autocomplete="off" placeholder="输入感兴趣的关键字">
            <a href="javascript:;" class="header-icon waves-effect waves-circle waves-light" id="search">
                <i class="icon icon-lg icon-search"></i>
            </a>
        </div>
        
        
        <a href="javascript:;" class="header-icon waves-effect waves-circle waves-light" id="menuShare">
            <i class="icon icon-lg icon-share-alt"></i>
        </a>
        
    </div>
</header>
<header class="content-header post-header">

    <div class="container fade-scale">
        <h1 class="title">快速排序和归并排序的时间复杂度分析——通俗易懂</h1>
        <h5 class="subtitle">
            
                <time datetime="2020-05-08T18:28:16.000Z" itemprop="datePublished" class="page-time">
  2020-05-09
</time>


	<ul class="article-category-list"><li class="article-category-list-item"><a class="article-category-list-link" href="/blog/categories/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/">数据结构与算法</a></li></ul>

            
        </h5>
    </div>

    


</header>


<div class="container body-wrap">
    
    <aside class="post-widget">
        <nav class="post-toc-wrap post-toc-shrink" id="post-toc">
            <h4>TOC</h4>
            <ol class="post-toc"><li class="post-toc-item post-toc-level-1"><a class="post-toc-link" href="#一、前言"><span class="post-toc-number">1.</span> <span class="post-toc-text">一、前言</span></a></li><li class="post-toc-item post-toc-level-1"><a class="post-toc-link" href="#二、正文"><span class="post-toc-number">2.</span> <span class="post-toc-text">二、正文</span></a><ol class="post-toc-child"><li class="post-toc-item post-toc-level-2"><a class="post-toc-link" href="#2-1-归并排序的时间复杂度分析"><span class="post-toc-number">2.1.</span> <span class="post-toc-text">2.1 归并排序的时间复杂度分析</span></a></li><li class="post-toc-item post-toc-level-2"><a class="post-toc-link" href="#2-2-快速排序的时间复杂度"><span class="post-toc-number">2.2.</span> <span class="post-toc-text">2.2 快速排序的时间复杂度</span></a></li></ol></li><li class="post-toc-item post-toc-level-1"><a class="post-toc-link" href="#三、总结"><span class="post-toc-number">3.</span> <span class="post-toc-text">三、总结</span></a></li></ol>
        </nav>
    </aside>


<article id="post-通俗易懂的归并排序和快速排序时间复杂度分析"
  class="post-article article-type-post fade" itemprop="blogPost">

    <div class="post-card">
        <h1 class="post-card-title">快速排序和归并排序的时间复杂度分析——通俗易懂</h1>
        <div class="post-meta">
            <time class="post-time" title="2020-05-09 02:28:16" datetime="2020-05-08T18:28:16.000Z"  itemprop="datePublished">2020-05-09</time>

            
	<ul class="article-category-list"><li class="article-category-list-item"><a class="article-category-list-link" href="/blog/categories/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/">数据结构与算法</a></li></ul>



            
<span id="busuanzi_container_page_pv" title="文章总阅读量" style='display:none'>
    <i class="icon icon-eye icon-pr"></i><span id="busuanzi_value_page_pv"></span>
</span>


        </div>
        <div class="post-content" id="post-content" itemprop="postContent">
            <h1 id="一、前言"><a href="#一、前言" class="headerlink" title="一、前言"></a>一、前言</h1><p>&emsp;&emsp;今天面试的时候，被问到归并排序的时间复杂度，这个大家都知道是<code>O（nlogn）</code>，但是面试官又继续问，怎么推导出来的。这我就有点懵了，因为之前确实没有去真正理解这个时间复杂度是如何得出的，于是就随便答了一波（理解了之后，发现面试的时候答错了……）。</p>
<p>&emsp;&emsp;归并排序和快速排序，是算法中，非常重要的两个知识点，同时也是在面试中被问的非常频繁的内容，我明知如此，却没有彻底理解，真是太不应该了。所以，今天这篇博客就来分析一下这两种排序算法的时间复杂度是如何得出的。我查了许多篇博客，很多都是通过公式进行分析，十分难理解，下面我就结合自己的理解，使用通俗易懂的方式进行描述（为了好理解，可能会有些啰嗦）。</p>
<br>

<h1 id="二、正文"><a href="#二、正文" class="headerlink" title="二、正文"></a>二、正文</h1><h2 id="2-1-归并排序的时间复杂度分析"><a href="#2-1-归并排序的时间复杂度分析" class="headerlink" title="2.1 归并排序的时间复杂度分析"></a>2.1 归并排序的时间复杂度分析</h2><p>&emsp;&emsp;了解归并排序的应该都知道，归并排序的时间复杂度是<code>O（nlogn）</code>，且这个时间复杂度是稳定的，不随需要排序的序列不同而产生波动。那这个时间复杂度是如何得来的呢？我们可以这样分析，假设我们需要对一个包含<code>n</code>个数的序列使用归并排序，并且使用的是递归的实现方式，那么过程如下：</p>
<ul>
<li>递归的第一层，将<code>n</code>个数划分为<code>2</code>个子区间，每个子区间的数字个数为<code>n/2</code>；</li>
<li>递归的第二层，将<code>n</code>个数划分为<code>4</code>个子区间，每个子区间的数字个数为<code>n/4</code>；</li>
<li>递归的第三层，将<code>n</code>个数划分为<code>8</code>个子区间，每个子区间的数字个数为<code>n/8</code>;</li>
</ul>
<p>&emsp;&emsp;……</p>
<ul>
<li>递归的第<code>logn</code>层，将<code>n</code>个数划分为<code>n</code>个子区间，每个子区间的数字个数为<code>1</code>；</li>
</ul>
<p>&emsp;&emsp;我们知道，归并排序的过程中，需要对当前区间进行对半划分，直到区间的长度为<code>1</code>。也就是说，每一层的子区间，长度都是上一层的<code>1/2</code>。<strong>这也就意味着，当划分到第logn层的时候，子区间的长度就是1了</strong>。而归并排序的<code>merge</code>操作，则是从最底层开始（子区间为<code>1</code>的层），对相邻的两个子区间进行合并，过程如下：</p>
<ul>
<li>在第<code>logn</code>层（最底层），每个子区间的长度为<code>1</code>，共<code>n</code>个子区间，每相邻两个子区间进行合并，总共合并<code>n/2</code>次。<code>n</code>个数字都会被遍历一次，所有这一层的总时间复杂度为<code>O（n）</code>；</li>
</ul>
<p>&emsp;&emsp;……</p>
<ul>
<li>在第二层，每个子区间长度为<code>n/4</code>，总共有<code>4</code>个子区间，每相邻两个子区间进行合并，总共合并<code>2</code>次。<code>n</code>个数字都会被遍历一次，所以这一层的总时间复杂度为<code>O（n）</code>；</li>
<li>在第一层，每个子区间长度为<code>n/2</code>，总共有<code>2</code>个子区间，只需要合并一次。<code>n</code>个数字都会被遍历一次，所以这一层的总时间复杂度为<code>O（n）</code>；</li>
</ul>
<p>&emsp;&emsp;通过上面的过程我们可以发现，对于每一层来说，在合并所有子区间的过程中，<code>n</code>个元素都会被操作一次，所以每一层的时间复杂度都是<code>O（n）</code>。而之前我们说过，归并排序划分子区间，将子区间划分为只剩<code>1</code>个元素，需要划分<code>logn</code>次。<strong>每一层的时间复杂度为O（n），共有logn层，所以归并排序的时间复杂度就是O（nlogn）</strong>。</p>
<p>&emsp;&emsp;上面的描述算是非常详细了，应该不会太难理解。如果上面的过程还是不太理解，那么我们通过另外一种更直观的方式进行分析。上面描述的是递归的过程，下面我们通过非递归（迭代）方式实现的归并排序，再来分析一波，这种方式更加直观（为什么不直接通过非递归的方式描述，而是先通过递归的方式分析，是因为上面的过程也可以用来分析快速排序）。下面是通过非递归方式实现的归并排序代码，其中有两处分析时间复杂度的关键点，我标注出来了（重点关注注释）：</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * 此方法用来定义子区间大小，子区间大小从1-&gt;2-&gt;4-&gt;8 ... -&gt;n/2</span></span><br><span class="line"><span class="comment"> * 可以近似地认为进行了logn次</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title">merge</span><span class="params">(<span class="keyword">int</span>[] arr)</span> </span>&#123;</span><br><span class="line">    <span class="comment">// 关键点1：划分子区间，每一次的子区间长度是上一次的两倍，所以这个循环需要执行logn次</span></span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">int</span> i = <span class="number">1</span>;i&lt;arr.length;i *= <span class="number">2</span>)&#123;</span><br><span class="line">        <span class="comment">// 关键点2：此方法每次执行的时间复杂度为O（n），具体看下方</span></span><br><span class="line">        mergeSort(arr,i);</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"></span><br><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * 以下方法，每次执行的时间复杂度都是O（n），</span></span><br><span class="line"><span class="comment"> * 因为需要将arr数组的每gap个数子，作为一个子区间，</span></span><br><span class="line"><span class="comment"> * 然后对相邻的两个子区间执行归并排序的merge操作，</span></span><br><span class="line"><span class="comment"> * 所以在这个方法中，arr数组中的每一个数都会在merge操作中，</span></span><br><span class="line"><span class="comment"> * 被处理一次，所以下面这个方法的时间复杂度为O（n）</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title">mergeSort</span><span class="params">(<span class="keyword">int</span>[] arr, <span class="keyword">int</span> gap)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">int</span>[] tmp = <span class="keyword">new</span> <span class="keyword">int</span>[arr.length];</span><br><span class="line">    <span class="keyword">int</span> index = <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">int</span> start1 = <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">int</span> end1 = start1 + gap - <span class="number">1</span>;</span><br><span class="line">    <span class="keyword">int</span> start2 = end1 + <span class="number">1</span>;</span><br><span class="line">    <span class="keyword">int</span> end2 = (start2 + gap - <span class="number">1</span>)&gt;=arr.length?arr.length-<span class="number">1</span>:start2+gap-<span class="number">1</span>;</span><br><span class="line">    <span class="keyword">while</span>(start2&lt;arr.length)&#123;</span><br><span class="line">        <span class="keyword">while</span>(start1&lt;=end1&amp;&amp;start2&lt;=end2)&#123;</span><br><span class="line">            <span class="keyword">if</span>(arr[start1]&lt;arr[start2])&#123;</span><br><span class="line">                tmp[index++] = arr[start1++];</span><br><span class="line">            &#125;<span class="keyword">else</span>&#123;</span><br><span class="line">                tmp[index++] = arr[start2++];</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">while</span>(start1&lt;=end1)&#123;</span><br><span class="line">            tmp[index++] = arr[start1++];</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">while</span>(start2&lt;=end2)&#123;</span><br><span class="line">            tmp[index++] = arr[start2++];</span><br><span class="line">        &#125;</span><br><span class="line">        start1 = end2+<span class="number">1</span>;</span><br><span class="line">        end1 = start1 + gap - <span class="number">1</span>;</span><br><span class="line">        start2 = end1 + <span class="number">1</span>;</span><br><span class="line">        end2 = (start2 + gap - <span class="number">1</span>)&gt;=arr.length?arr.length-<span class="number">1</span>:start2+gap-<span class="number">1</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">while</span>(start1&lt;arr.length)&#123;</span><br><span class="line">        tmp[index++] = arr[start1++];</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">int</span> j = <span class="number">0</span>;j&lt;tmp.length;j++)&#123;</span><br><span class="line">        arr[j] = tmp[j];</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>&emsp;&emsp;上面的代码，<code>merge</code>方法中的循环需要循环<code>logn</code>次，每次循环都调用一次<code>mergeSort</code>方法，<code>mergeSort</code>方法的时间复杂度为<code>O（n）</code>，所以很容易得出归并排序的时间复杂度为<code>O（nlogn）</code>。</p>
<br>

<h2 id="2-2-快速排序的时间复杂度"><a href="#2-2-快速排序的时间复杂度" class="headerlink" title="2.2 快速排序的时间复杂度"></a>2.2 快速排序的时间复杂度</h2><p>&emsp;&emsp;了解快速排序的应该知道，快速排序的时间复杂度在<code>O（nlogn）~ O（n^2）</code>之间，下面我就来分别分析这两种情况：</p>
<p><strong>（一）快速排序的最好情况O（nlogn）</strong></p>
<p>&emsp;&emsp;这种情况下，其实和上面通过递归分析的归并排序很类似，理解了归并排序的时间复杂度分析，那这里应该也很好理解。快速排序的实现方式，就是在当前区间中选择一个轴，区间中所有比轴小的数都需要放到轴的左边，而比轴大的数则放到轴的右边。<strong>在理想的情况下，我们选取的轴刚好就是这个区间的中位数</strong>。也就是说，在操作之后，正好将区间分成了数字个数相等的左右两个子区间。此时就和归并排序基本一致了：</p>
<ul>
<li>递归的第一层，<code>n</code>个数被划分为<code>2</code>个子区间，每个子区间的数字个数为<code>n/2</code>；</li>
<li>递归的第二层，<code>n</code>个数被划分为<code>4</code>个子区间，每个子区间的数字个数为<code>n/4</code>；</li>
<li>递归的第三层，<code>n</code>个数被划分为<code>8</code>个子区间，每个子区间的数字个数为<code>n/8</code>;</li>
</ul>
<p>&emsp;&emsp;……</p>
<ul>
<li>递归的第<code>logn</code>层，<code>n</code>个数被划分为<code>n</code>个子区间，每个子区间的数字个数为<code>1</code>；</li>
</ul>
<p>&emsp;&emsp;以上过程与归并排序基本一致，而区别就是，归并排序是从最后一层开始进行<code>merge</code>操作，自底向上；而快速排序则是从第一层开始，交换区间中数字的位置，也就是自顶向下。但是，<code>merge</code>操作和快速排序的调换位置操作，时间复杂度是一样的，对于每一个区间，处理的时候，都需要遍历一次区间中的每一个元素。这也就意味着，快速排序和归并排序一样，每一层的总时间复杂度都是<code>O（n）</code>，因为需要对每一个元素遍历一次。而且在最好的情况下，同样也是有<code>logn</code>层，所以快速排序最好的时间复杂度为<code>O（nlogn）</code>。</p>
<br>

<p><strong>（二）快速排序的最坏情况O（n^2）</strong></p>
<p>&emsp;&emsp;下面我们再来说一说快速排序的最坏情况，这种情况就比较好理解了。什么是快速排序的最坏情况，那就是，<strong>对于每一个区间，我们在处理的时候，选取的轴刚好就是这个区间的最大值或者最小值</strong>。比如我们需要对<code>n</code>个数排序，而每一次进行处理的时候，选取的轴刚好都是区间的最小值。于是第一次操作，在经过调换元素顺序的操作后，最小值被放在了第一个位置，剩余<code>n-1</code>个数占据了<code>2到n</code>个位置；第二次操作，处理剩下的<code>n-1</code>个元素，又将这个子区间的最小值放在了当前区间的第<code>1</code>个位置，以此类推……每次操作，都只能将最小值放到第一个位置，而剩下的元素，则没有任何变化。所以对于<code>n</code>个数来说，需要操作<code>n</code>次，才能为<code>n</code>个数排好序。而每一次操作都需要遍历一次剩下的所有元素，这个操作的时间复杂度是<code>O（n）</code>，所以总时间复杂度为<code>O（n^2）</code>。</p>
<p>&emsp;&emsp;其实上面的过程，我们可以换一个角度理解：每次操作，找出最小值放到剩余区间的第一个位置，这不就是<strong>选择排序</strong>的实现方式吗？而选择排序的时间复杂度就是<code>O（n^2）</code>，所以上面的过程也就<code>O（n^2）</code>。</p>
<br>

<h1 id="三、总结"><a href="#三、总结" class="headerlink" title="三、总结"></a>三、总结</h1><p>&emsp;&emsp;以上内容，就是我基于自己的理解，对快速排序和归并排序时间复杂度的分析。为了更好理解，我的描述都尽可能的详细，所以可能会有点啰嗦，但是我认为还是很通俗易懂的。希望这篇博客能够为之前对这两种排序算法理解不是特别清晰的人提供帮助，同时，若上面的内容存在错误或不足，欢迎指正或补充。</p>

        </div>

        <blockquote class="post-copyright">
    
    <div class="content">
        
<span class="post-time">
    最后更新时间：<time datetime="2020-05-08T19:52:55.485Z" itemprop="dateUpdated">2020-05-09 03:52:55</time>
</span><br>


        
        世界是个球，前方总有路！
        
    </div>
    
    <footer>
        <a href="http://tewuyiang.gitee.io/blog">
            <img src="/blog/img/avatar.jpg" alt="特务依昂">
            特务依昂
        </a>
    </footer>
</blockquote>

        


        <div class="post-footer">
            
	<ul class="article-tag-list" itemprop="keywords"><li class="article-tag-list-item"><a class="article-tag-list-link" href="/blog/tags/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/" rel="tag">数据结构与算法</a></li></ul>


            
<div class="page-share-wrap">
    

<div class="page-share" id="pageShare">
    <ul class="reset share-icons">
      <li>
        <a class="weibo share-sns" target="_blank" href="http://service.weibo.com/share/share.php?url=http://tewuyiang.gitee.io/blog/%E9%80%9A%E4%BF%97%E6%98%93%E6%87%82%E7%9A%84%E5%BD%92%E5%B9%B6%E6%8E%92%E5%BA%8F%E5%92%8C%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F%E6%97%B6%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6%E5%88%86%E6%9E%90/&title=《快速排序和归并排序的时间复杂度分析——通俗易懂》 — 博客主页&pic=http://tewuyiang.gitee.io/blog/img/avatar.jpg" data-title="微博">
          <i class="icon icon-weibo"></i>
        </a>
      </li>
      <li>
        <a class="weixin share-sns wxFab" href="javascript:;" data-title="微信">
          <i class="icon icon-weixin"></i>
        </a>
      </li>
      <li>
        <a class="qq share-sns" target="_blank" href="http://connect.qq.com/widget/shareqq/index.html?url=http://tewuyiang.gitee.io/blog/%E9%80%9A%E4%BF%97%E6%98%93%E6%87%82%E7%9A%84%E5%BD%92%E5%B9%B6%E6%8E%92%E5%BA%8F%E5%92%8C%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F%E6%97%B6%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6%E5%88%86%E6%9E%90/&title=《快速排序和归并排序的时间复杂度分析——通俗易懂》 — 博客主页&source=一个未来程序员的博客~~~" data-title=" QQ">
          <i class="icon icon-qq"></i>
        </a>
      </li>
      <li>
        <a class="facebook share-sns" target="_blank" href="https://www.facebook.com/sharer/sharer.php?u=http://tewuyiang.gitee.io/blog/%E9%80%9A%E4%BF%97%E6%98%93%E6%87%82%E7%9A%84%E5%BD%92%E5%B9%B6%E6%8E%92%E5%BA%8F%E5%92%8C%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F%E6%97%B6%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6%E5%88%86%E6%9E%90/" data-title=" Facebook">
          <i class="icon icon-facebook"></i>
        </a>
      </li>
      <li>
        <a class="twitter share-sns" target="_blank" href="https://twitter.com/intent/tweet?text=《快速排序和归并排序的时间复杂度分析——通俗易懂》 — 博客主页&url=http://tewuyiang.gitee.io/blog/%E9%80%9A%E4%BF%97%E6%98%93%E6%87%82%E7%9A%84%E5%BD%92%E5%B9%B6%E6%8E%92%E5%BA%8F%E5%92%8C%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F%E6%97%B6%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6%E5%88%86%E6%9E%90/&via=http://tewuyiang.gitee.io/blog" data-title=" Twitter">
          <i class="icon icon-twitter"></i>
        </a>
      </li>
      <li>
        <a class="google share-sns" target="_blank" href="https://plus.google.com/share?url=http://tewuyiang.gitee.io/blog/%E9%80%9A%E4%BF%97%E6%98%93%E6%87%82%E7%9A%84%E5%BD%92%E5%B9%B6%E6%8E%92%E5%BA%8F%E5%92%8C%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F%E6%97%B6%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6%E5%88%86%E6%9E%90/" data-title=" Google+">
          <i class="icon icon-google-plus"></i>
        </a>
      </li>
    </ul>
 </div>



    <a href="javascript:;" id="shareFab" class="page-share-fab waves-effect waves-circle">
        <i class="icon icon-share-alt icon-lg"></i>
    </a>
</div>



        </div>
    </div>

    
<nav class="post-nav flex-row flex-justify-between">
  
    <div class="waves-block waves-effect prev">
      <a href="/blog/%E7%AE%80%E5%8D%95%E8%B0%88%E8%B0%88Spring%E7%9A%84IOC%E5%AE%9E%E7%8E%B0/" id="post-prev" class="post-nav-link">
        <div class="tips"><i class="icon icon-angle-left icon-lg icon-pr"></i> Prev</div>
        <h4 class="title">简单谈谈Spring的IoC以及bean的生命周期</h4>
      </a>
    </div>
  

  
    <div class="waves-block waves-effect next">
      <a href="/blog/Redis%E4%B8%BA%E4%BB%80%E4%B9%88%E6%98%AF%E5%8D%95%E7%BA%BF%E7%A8%8B/" id="post-next" class="post-nav-link">
        <div class="tips">Next <i class="icon icon-angle-right icon-lg icon-pl"></i></div>
        <h4 class="title">Redis为什么是单线程</h4>
      </a>
    </div>
  
</nav>



    




















</article>



</div>

        <footer class="footer">
    <div class="top">
        
<p>
    <span id="busuanzi_container_site_uv" style='display:none'>
        站点总访客数：<span id="busuanzi_value_site_uv"></span>
    </span>
    <span id="busuanzi_container_site_pv" style='display:none'>
        站点总访问量：<span id="busuanzi_value_site_pv"></span>
    </span>
</p>


        <p>
            
                <span><a href="/blog/atom.xml" target="_blank" class="rss" title="rss"><i class="icon icon-lg icon-rss"></i></a></span>
            
            <span>博客内容遵循 <a rel="license noopener" href="https://creativecommons.org/licenses/by-nc-sa/4.0/deed.zh" target="_blank">知识共享 署名 - 非商业性 - 相同方式共享 4.0 国际协议</a></span>
        </p>
    </div>
    <div class="bottom">
        <p><span>特务依昂 &copy; 2015 - 2020</span>
            <span>
                
                Power by <a href="http://hexo.io/" target="_blank">Hexo</a> Theme <a href="https://github.com/yscoder/hexo-theme-indigo" target="_blank">indigo</a>
            </span>
        </p>
    </div>
</footer>

    </main>
    <div class="mask" id="mask"></div>
<a href="javascript:;" id="gotop" class="waves-effect waves-circle waves-light"><span class="icon icon-lg icon-chevron-up"></span></a>



<div class="global-share" id="globalShare">
    <ul class="reset share-icons">
      <li>
        <a class="weibo share-sns" target="_blank" href="http://service.weibo.com/share/share.php?url=http://tewuyiang.gitee.io/blog/%E9%80%9A%E4%BF%97%E6%98%93%E6%87%82%E7%9A%84%E5%BD%92%E5%B9%B6%E6%8E%92%E5%BA%8F%E5%92%8C%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F%E6%97%B6%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6%E5%88%86%E6%9E%90/&title=《快速排序和归并排序的时间复杂度分析——通俗易懂》 — 博客主页&pic=http://tewuyiang.gitee.io/blog/img/avatar.jpg" data-title="微博">
          <i class="icon icon-weibo"></i>
        </a>
      </li>
      <li>
        <a class="weixin share-sns wxFab" href="javascript:;" data-title="微信">
          <i class="icon icon-weixin"></i>
        </a>
      </li>
      <li>
        <a class="qq share-sns" target="_blank" href="http://connect.qq.com/widget/shareqq/index.html?url=http://tewuyiang.gitee.io/blog/%E9%80%9A%E4%BF%97%E6%98%93%E6%87%82%E7%9A%84%E5%BD%92%E5%B9%B6%E6%8E%92%E5%BA%8F%E5%92%8C%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F%E6%97%B6%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6%E5%88%86%E6%9E%90/&title=《快速排序和归并排序的时间复杂度分析——通俗易懂》 — 博客主页&source=一个未来程序员的博客~~~" data-title=" QQ">
          <i class="icon icon-qq"></i>
        </a>
      </li>
      <li>
        <a class="facebook share-sns" target="_blank" href="https://www.facebook.com/sharer/sharer.php?u=http://tewuyiang.gitee.io/blog/%E9%80%9A%E4%BF%97%E6%98%93%E6%87%82%E7%9A%84%E5%BD%92%E5%B9%B6%E6%8E%92%E5%BA%8F%E5%92%8C%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F%E6%97%B6%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6%E5%88%86%E6%9E%90/" data-title=" Facebook">
          <i class="icon icon-facebook"></i>
        </a>
      </li>
      <li>
        <a class="twitter share-sns" target="_blank" href="https://twitter.com/intent/tweet?text=《快速排序和归并排序的时间复杂度分析——通俗易懂》 — 博客主页&url=http://tewuyiang.gitee.io/blog/%E9%80%9A%E4%BF%97%E6%98%93%E6%87%82%E7%9A%84%E5%BD%92%E5%B9%B6%E6%8E%92%E5%BA%8F%E5%92%8C%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F%E6%97%B6%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6%E5%88%86%E6%9E%90/&via=http://tewuyiang.gitee.io/blog" data-title=" Twitter">
          <i class="icon icon-twitter"></i>
        </a>
      </li>
      <li>
        <a class="google share-sns" target="_blank" href="https://plus.google.com/share?url=http://tewuyiang.gitee.io/blog/%E9%80%9A%E4%BF%97%E6%98%93%E6%87%82%E7%9A%84%E5%BD%92%E5%B9%B6%E6%8E%92%E5%BA%8F%E5%92%8C%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F%E6%97%B6%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6%E5%88%86%E6%9E%90/" data-title=" Google+">
          <i class="icon icon-google-plus"></i>
        </a>
      </li>
    </ul>
 </div>


<div class="page-modal wx-share" id="wxShare">
    <a class="close" href="javascript:;"><i class="icon icon-close"></i></a>
    <p>扫一扫，分享到微信</p>
    <img src="" alt="微信分享二维码">
</div>




    <script src="//cdn.bootcss.com/node-waves/0.7.4/waves.min.js"></script>
<script>
var BLOG = { ROOT: '/blog/', SHARE: true, REWARD: false };


</script>

<script src="//unpkg.com/hexo-theme-material-indigo@latest/js/main.min.js"></script>


<div class="search-panel" id="search-panel">
    <ul class="search-result" id="search-result"></ul>
</div>
<template id="search-tpl">
<li class="item">
    <a href="{path}" class="waves-block waves-effect">
        <div class="title ellipsis" title="{title}">{title}</div>
        <div class="flex-row flex-middle">
            <div class="tags ellipsis">
                {tags}
            </div>
            <time class="flex-col time">{date}</time>
        </div>
    </a>
</li>
</template>

<script src="//unpkg.com/hexo-theme-material-indigo@latest/js/search.min.js" async></script>






<script async src="//busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script>



<script>
(function() {
    var OriginTitile = document.title, titleTime;
    document.addEventListener('visibilitychange', function() {
        if (document.hidden) {
            document.title = '人呢，怎么不见了！';
            clearTimeout(titleTime);
        } else {
            document.title = '(つェ⊂)咦!欢迎回来!';
            titleTime = setTimeout(function() {
                document.title = OriginTitile;
            },2000);
        }
    });
})();
</script>



</body>
</html>
